Hoffman-Singletonov graf
Hoffman-Singletonov graf | |
---|---|
![]() | |
Ime | Alan Jerome Hoffman Robert R. Singleton |
Točke | 50 |
Povezave | 175 |
Polmer | 2 |
Premer | 2 |
Notranji obseg | 5 |
Avtomorfizem | 252.000 (PSU(3,52):2)[1] |
Kromatično število | 4 |
Kromatični indeks | 7[2] |
Značilnosti | krepkoregularen simetričen Hamiltonov celoštevilski kletka Mooreov |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Hoffman_singleton_graph_circle2.gif/250px-Hoffman_singleton_graph_circle2.gif)
Hoffman-Singletonov graf je v teoriji grafov 7-regularni neusmerjeni graf s 50 točkami in 175 povezavami. Je edini krepkopovezani graf s parametri (50,7,0,1).[3] Skonstruirala sta ga Alan Jerome Hoffman in Robert R. Singleton pri klasifikaciji vseh Mooreovih grafov. Hoffman-Singletonov graf je Mooreov graf z največjim znanim redom.[4] Ker je Mooreov graf v katerem ima vsaka točka stopnjo 7, njegov notranji obseg pa je 5, je tudi (7,5)-kletka.
Konstrukcija
[uredi | uredi kodo]Preprosta neposredna konstrukcija je naslednja: vzame se pet petkotnikov Ph in pet pentagramov Qi, tako da je točka j iz Ph sosednja točkam j-1,j+1 v Ph, točka j iz Qi pa je sosednja točkam j-2,j+2 v Qi. Nato se poveže točko j iz Ph s točko hi+j iz Qi. (Vsi indeksi mod 5.)
Algebrske značilnosti
[uredi | uredi kodo]Grupa avtomorfizmov Hoffman-Singletonovega grafa je grupa reda 252.000 izomorfna PΣU(3,52), poldirektnemu produktu projektivni posebni unitarni grupi PSU(3,52) s ciklično grupo reda 2, tvorjeno s Frobeniusovim avtomorfizmom. Hoffman-Singletonov graf je točkovno in razdaljnoprehoden, ter zato simetričen.
Karakteristični polinom Hoffman-Singletonovega grafa je:
Hoffman-Singletonov graf je zaradi tega celoštevilski graf: njegov spekter v celoti sestavljajo le cela števila.
Sklici
[uredi | uredi kodo]- ↑ Hafner (2003).
- ↑ Royle (2004).
- ↑ Brouwer.
- ↑ Hoffman; Singleton (1960).
Viri
[uredi | uredi kodo]- Benson, C. T.; Losey, N. E. (1971), »On a graph of Hoffman and Singleton«, Journal of Combinatorial Theory, Series B, 11: 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
- Brouwer, Andries Evert. »Hoffman-Singleton graph« (v angleščini).
- Hafner, P. R. (2003), »The Hoffman-Singleton Graph and Its Automorphisms«, J. Algebraic Combin., 18: 7–12
- Hoffman, Alan Jerome; Singleton, Robert R. (1960), »Moore graphs with diameter 2 and 3« (PDF), IBM Journal of Research and Development, 5 (4): 497–504, MR 0140437
- Holton, D. A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, str. 186 in 190, ISBN 0-521-43594-3
- Royle, G. (28. september 2004), »Re: What is the Edge Chromatic Number of Hoffman-Singleton?«, GRAPHNET@istserv.nodak.edu posting. (v angleščini)[mrtva povezava]